package ru.ifmo.cppsc.grammar;



import java.util.*;


/**
 * Author: Olga Komaleva
 * Date: Jun 15, 2008
 */
public class ProperGrammar extends Grammar {


    public ProperGrammar(String fileName) {
        loadAsXML(fileName);
        //load(fileName);

        deleteUnachievableSymbols();
        deleteEpsilonProductions();
        //deleteCycles();
    }


    private void deleteUnachievableSymbols() {
        Set<Symbol> terms = new HashSet<Symbol>();
        Set<Symbol> nonterms = new HashSet<Symbol>();
        ArrayList<Production> prods = new ArrayList<Production>();

        nonterms.add(START);

        boolean areChanged = true;
        while (areChanged) {
            areChanged = false;
            for (Production production : getProductions()) {
                if (nonterms.contains(production.getLeft())) {
                    for (Symbol symbol : production.getRight()) {

                        if (symbol != EPSILON) {
                            if (isTerminal(symbol)) {
                                areChanged = areChanged || terms.add(symbol);
                            } else {
                                areChanged = areChanged || nonterms.add(symbol);
                            }
                        }
                    }
                }
            }
        }

        for (Production production : getProductions()) {
            if (nonterms.contains(production.getLeft())) {
                prods.add(production);
            }
        }
        resetGrammar(new ArrayList<Symbol>(terms), new ArrayList<Symbol>(nonterms), prods);
    }

    private void deleteEpsilonProductions() {
        ArrayList<Symbol> nonterms = findEpsilonAchievable();

        for (Symbol nt : nonterms) {
            for (Production production : getProductions()) {
                productions.addAll(deleteEpsilonProduction(production, nt));
            }
        }

        if (nonterms.contains(START)) {
            Symbol nt = addNonTerminal("S1");
            productions.add(new Production(nt, new Symbol[]{EPSILON}, ""));
            productions.add(new Production(nt, new Symbol[]{START}, ""));
            START = nt;
        }
    }

    private ArrayList<Production> deleteEpsilonProduction(Production production, Symbol nt) {
        ArrayList<Production> prods = new ArrayList<Production>();
        for (int i = 0; i < production.getRight().length; i++) {
            if (production.getRight()[i] == nt) {
                int l = production.getRight().length - 1 - i;

                int n = prods.size();
                for (int s = 0; s < n; s++) {
                    Production p = prods.get(s);
                    if (p.getRight().length > 1) {
                        prods.add(p.removeFromRight(p.getRight().length - 1 - l));
                    }
                }
                if (production.getRight().length > 1) {
                    prods.add(production.removeFromRight(i));
                }
            }
        }

        return prods;
    }

    private ArrayList<Symbol> findEpsilonAchievable() {
        ArrayList<Symbol> nonterms = new ArrayList<Symbol>();

        for (Production production : getProductions()) {
            if ((production.getRight().length == 1) && (production.getRight()[0] == EPSILON)) {
                nonterms.add(production.getLeft());
                productions.remove(production);
            }
        }

        boolean areChanged = true;
        while (areChanged) {
            areChanged = false;
            for (Production production : getProductions()) {
                if (!nonterms.contains(production.getLeft())) {
                    int i = 0;
                    while (i < production.getRight().length) {
                        if (!nonterms.contains(production.getRight()[i])) {
                            break;
                        }
                        i++;
                    }
                    if (i == production.getRight().length) {
                        areChanged = areChanged || nonterms.add( production.getLeft());
                    }
                }
            }
        }


        return nonterms;
    }

    private void deleteCycles() {
        boolean achive[][] = achievable();
        ArrayList<Production> toRemoved = new ArrayList<Production>();
        ArrayList<Production> toAdded = new ArrayList<Production>();
        for (Production p : getProductions()) {
            if ((p.getRight().length == 1) && (p.getRight()[0] != EPSILON)
                    && !isTerminal(p.getRight()[0])) {
                toRemoved.add(p);
            } else {
                int l = p.getLeft().getId();
                for (int i = 0; i < achive[l].length; i++) {
                    if (achive[i][l]) {
                        toAdded.add(new Production(getSymbolById(i), p.getRight(), ""));
                        for (Symbol s2 : p.getRight()) {
                            if (p.getLeft() == s2) {
                                toAdded.add(new Production(getSymbolById(i), new Symbol[]{getSymbolById(l)}, ""));
                            }
                        }
                    }
                }
            }
        }

        productions.removeAll(toRemoved);
        productions.addAll(toAdded);
    }

    private boolean[][] achievable() {
        Symbol[] nonterminals = getNonTerminals();
        boolean areChanged = true;
        boolean achive[][] = new boolean[nonterminals.length][nonterminals.length];

        for (Production p : getProductions()) {
            if ((p.getRight().length == 1) && (p.getRight()[0] != EPSILON)
                    && !isTerminal(p.getRight()[0])) {
                achive[p.getLeft().getId()][p.getRight()[0].getId()] = true;
            }
        }

        while (areChanged) {
            areChanged = false;
            for (Symbol a : nonterminals) {
                for (Symbol b : nonterminals) {
                    if (achive[a.getId()][b.getId()]) {
                        for (int i = 0; i < achive[b.getId()].length; i++) {
                            if (achive[b.getId()][i]) {
                                areChanged = areChanged || !achive[a.getId()][i];
                                achive[a.getId()][i] = true;
                            }
                        }
                    }
                }
            }
        }

        return achive;
    }


}
